#define _CRT_SECURE_NO_WARNINGS
#include <unordered_map>
#include <iostream>
using namespace std;
class LRUCache {
    struct Node
    {
        Node* next, * prev;
        int key;
        int value;
        Node() :next(nullptr), prev(nullptr), key(0), value(0)
        {}
        Node(int _key, int _value) :next(nullptr), prev(nullptr), key(_key), value(_value)
        {}
    };
public:
    Node* head, * tail;
    unordered_map<int, Node*> hash;
    int capacity;
    int size;
    LRUCache(int _capacity) :capacity(_capacity), size(0) {
        head = new Node();
        tail = new Node();
        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        if (!hash.count(key))  return -1;
        Node* remove = hash[key];
        removeNode(remove);
        addNodeToHead(remove);
        return remove->value;
    }

    void put(int key, int value) {
        if (hash.count(key))
        {
            Node* remove = hash[key];
            remove->value = value;
            removeNode(remove);
            addNodeToHead(remove);
        }
        else
        {
            Node* newnode = new Node(key, value);
            hash.insert({ key, newnode });
            addNodeToHead(newnode);
            size++;
            if (size > capacity)
            {
                Node* remove = tail->prev;
                hash.erase(remove->key);
                removeNode(remove);
                size--;
            }
        }
    }
    void removeNode(Node* node)
    {
        node->prev->next = node->next;
        node->next->prev = node->prev;

    }
    void addNodeToHead(Node* node)
    {
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
        node->prev = head;
    }
};


int main()
{
    LRUCache lc(3);
    lc.put(1, 1);
    lc.put(2, 2);
    lc.put(3, 3);
    return 0;
}